#include <cstdlib>
void mergesort(int a[], int left, int right) {
	if(left>=right)
		return;
	int mid = (left+right)/2;
	mergesort(a,left,mid);
	mergesort(a,mid+1,right);

	void merge(int a[],int left, int mid, int right);
	merge(a,left,mid,right);
}

void merge(int a[],int left, int mid, int right) {
	int *b = (int*)malloc((right-left+1)*sizeof(int));
	int i,j,k;
	for(i = left, j = mid+1, k = 0; i <= mid && j <= right && k <= right-left; )
		if ( a[i] <= a[j] )
			b[k++] = a[i++];
		else
			b[k++] = a[j++];
	while (i <= mid)
		b[k++] = a[i++];
	while (j <= right)
		b[k++] = a[j++];
	for (i = left, k = 0; i <= right && k <= right-left;)
		a[i++] = b[k++];
	free(b);
}